home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / X11 / wais / ir / irhash.c < prev    next >
C/C++ Source or Header  |  1995-05-09  |  12KB  |  374 lines
  1. /* WIDE AREA INFORMATION SERVER SOFTWARE:
  2.    No guarantees or restrictions.  See the readme file for the full standard
  3.    disclaimer.
  4.  
  5.    Brewster@think.com
  6. */
  7.  
  8. /* The memory hashtables for building an index. */
  9. /* -brewster 5/90 */
  10.  
  11. /* Change log:
  12.  * $Log:    irhash.c,v $
  13.  * Revision 1.16  92/03/20  11:04:33  jonathan
  14.  * Added code to handle switches for word_pairs and word_postition info.
  15.  * 
  16.  * Revision 1.15  92/02/12  13:26:28  jonathan
  17.  * Added "$Log" so RCS will put the log message in the header
  18.  * 
  19. */
  20.  
  21. /* main functions:
  22.  *   add_word
  23.  *   finished_add_word
  24.  *   look_up_word
  25.  *
  26.  * The idea is to store up a bunch of words before going to disk.
  27.  * A word entry points to where it will go on disk, and
  28.  * accumulates the entries before doing it.
  29.  *
  30.  * Some of the policy issues in this file are:
  31.  *   How much weight should the first occurance of a word in a document get
  32.  *   over the other occurances.  The first occurance should be worth more
  33.  *   so that words with 3 occurances of "dog" and not "cat"'s should not 
  34.  *   win out over 1 "dog" and 1 "cat" if the question is "Tell me about cats
  35.  *   torture dogs"
  36.  *   The extra weight is 5 at this point.
  37.  *
  38.  */
  39.  
  40. /* To Do:
  41.  *  done: Improve the hashing functions.
  42.  *  done: stop inserting into hash table after max number have been accumulated
  43.  *  done: make flush not flush buffers that are too big.
  44.  */
  45.  
  46. #include <ctype.h>
  47. #include <string.h>     /* for strlen(), memset() */
  48.  
  49. #include "panic.h"
  50. #include "cutil.h"
  51. #include "irfiles.h"
  52. #include "irhash.h"
  53. #include "stoplist.h"
  54. #include "irinv.h"
  55.  
  56. #ifdef UNIX
  57. #define PRINT_AS_INDEXING true /* also defined in irtfiles.c and irfiles.c */
  58. #else 
  59. #define PRINT_AS_INDEXING false
  60. #endif
  61.  
  62. /* ================================
  63.    ===  Word Occurance Buffers  ===
  64.    ================================ */
  65.  
  66. /* Word occurance buffers
  67.  * This is a simple memory allocator for use with the word memory hashtable.
  68.  * Since the buffers are tiny, this is done as a copy-sweep GC scheme.
  69.  * Oh, I long for the storage system of lisp.
  70.  */
  71. unsigned char *first_word_occurance_buffer = NULL;  /* allocate blocks out of this */
  72. unsigned char *last_word_occurance_buffer = NULL;
  73. long word_occurance_block_length = 256000;  /* maybe this should be larger? */
  74. unsigned char * word_occurance_free_ptr = NULL;
  75.  
  76. unsigned char *make_word_occurrance_block(size)
  77. long size;
  78.  
  79. {
  80.   /* allocates a word_occurance_block out of the buffers */
  81.   /* old way: s_malloc((size_t)size); */
  82.   /* returns a pointer to a piece of memory */
  83.   if(NULL == first_word_occurance_buffer){
  84.     /* initialize it */
  85.     first_word_occurance_buffer = 
  86.       (unsigned char *)s_malloc(MAX(word_occurance_block_length,
  87.                sizeof(size_t)+ size));
  88.     *(unsigned char **)first_word_occurance_buffer = NULL; /* set the end */
  89.     last_word_occurance_buffer = first_word_occurance_buffer;
  90.     word_occurance_free_ptr = first_word_occurance_buffer + sizeof(size_t);
  91.   }
  92.   if((long)word_occurance_free_ptr + size >= 
  93.      word_occurance_block_length + (long)last_word_occurance_buffer){
  94.     /* then allocate a new block */
  95.     unsigned char * new_block = (unsigned char *)s_malloc(MAX(word_occurance_block_length,
  96.                         sizeof(size_t)+ size));
  97.     *(unsigned char **)new_block = NULL; /* set the end of the chain */
  98.     *(unsigned char **)last_word_occurance_buffer = new_block;
  99.     word_occurance_free_ptr = new_block + sizeof(size_t);
  100.     last_word_occurance_buffer = new_block;
  101.   }
  102.   /* allocate away */    
  103.   { unsigned char * answer = word_occurance_free_ptr;
  104.     word_occurance_free_ptr += size;    
  105.     return(answer);  
  106.   }
  107. }
  108.  
  109. void free_word_occurance_block(block)
  110. unsigned char *block;
  111. {
  112.   /* this is not used with the new scheme, but is here in case
  113.      malloc is a win on some systems */
  114.   /* old way s_free(block); */
  115. }
  116.  
  117. static void flush_word_occur_bufs_internal
  118.   _AP((unsigned char* head_of_list));
  119.  
  120. static void flush_word_occur_bufs_internal(head_of_list)
  121. unsigned char* head_of_list;
  122. /* frees all word occurance buffers.  This should be done with care */
  123. {      
  124.   while(1){
  125.     unsigned char * next_block;
  126.     if(NULL == head_of_list)
  127.       break;
  128.     next_block = *(unsigned char **)head_of_list;
  129.     s_free(head_of_list);
  130.     head_of_list = next_block;
  131.   }
  132. }
  133.  
  134. void flush_word_occurance_buffers()
  135. {
  136.   /* frees all word occurance buffers.  This should be done with care */
  137.   flush_word_occur_bufs_internal(first_word_occurance_buffer);
  138.   first_word_occurance_buffer = NULL;
  139.   word_occurance_free_ptr = NULL;
  140.   last_word_occurance_buffer = NULL;
  141. }
  142.  
  143.  
  144. /* ---------------------------------------------------- */
  145. static hash_entry* look_up_word _AP((char* word,hashtable*
  146.                      the_word_memory_hashtable));
  147.   
  148. static hash_entry* 
  149. look_up_word(word,the_word_memory_hashtable)
  150. char* word;
  151. hashtable* the_word_memory_hashtable;
  152. {
  153.   hash_entry * answer = get_hash(word, the_word_memory_hashtable);
  154.   
  155.   if(NULL != answer)
  156.     return(answer);
  157.   else{
  158.     hash_entry wrd_entry;
  159.     answer = put_hash(word, the_word_memory_hashtable, &wrd_entry);
  160.     answer->number_of_occurances = 0;
  161.     answer->memory_ptr = 
  162.       make_word_occurrance_block(WORD_MEMORY_INIT_BLOCK_SIZE);
  163.     answer->current_memory_ptr = answer->memory_ptr;
  164.     answer->memory_size = WORD_MEMORY_INIT_BLOCK_SIZE;
  165.     answer->current_doc_id = 0;
  166.     return(answer);
  167.   }
  168. }
  169.  
  170. static unsigned char add_weight _AP((long current_weight,long new_weight));
  171.  
  172. static unsigned char 
  173. add_weight(current_weight,new_weight)
  174. long current_weight;
  175. long new_weight;
  176. /* add a new weight to the existing one */
  177. {
  178.   /* this should be smarter than this, like doing the log or something */
  179.   if(127 < (current_weight + new_weight)){
  180.     /* the max char.  should be 255, but does not work on all compilers */
  181.     return(127);
  182.   }
  183.   else{
  184.     return(current_weight + new_weight);
  185.   }
  186. }
  187.  
  188. static unsigned char* more_memory _AP((unsigned char* current_memory_ptr,
  189.                        long current_memory_size,
  190.                        long new_size));
  191.  
  192. static unsigned char* more_memory(current_memory_ptr,current_memory_size,new_size)
  193. unsigned char* current_memory_ptr;
  194. long current_memory_size;
  195. long new_size;
  196. /* Allocates more memory for a hash_entry.  It transfers all the bytes 
  197.  * from the old to the new and then returns the new.
  198.  */
  199. {
  200.   unsigned char* new_memory = NULL;
  201.   if(current_memory_size > new_size){
  202.     panic("trying to contract a hash_entry block.  This is not right\n");
  203.   }
  204.   new_memory = make_word_occurrance_block(new_size);
  205.   if(NULL == new_memory){
  206.     panic("Out of memory.");
  207.   }
  208.   memset(new_memory, 0, new_size);
  209.   memmove(new_memory, current_memory_ptr, (size_t)current_memory_size); 
  210.   return(new_memory);
  211. }
  212.  
  213. static long more_memory_size _AP((long current_size,
  214.                   long number_of_occurances));
  215.  
  216. static long more_memory_size(current_size,number_of_occurances)
  217. long current_size;
  218. long number_of_occurances;
  219. /* This is pretty important to get right.  This is a place holder */
  220. {
  221.   return(MAX(2 * current_size, WORD_MEMORY_INIT_BLOCK_SIZE));
  222. }
  223.  
  224. long write_bytes_to_memory(value,size,ptr)
  225. long value;
  226. long size;
  227. unsigned char* ptr;
  228. {
  229.   /* writes the number into memory lsb first.  
  230.      returns the number of bytes written */
  231.   long i;
  232.   long original_value = value;
  233.  
  234.   if(size < 0) /* paranoia */
  235.     panic("attempting to write a negative number of bytes");
  236.  
  237.   ptr += size; /* start at the end of the block and write backwards */
  238.   for (i = 0; i < size; i++){
  239.     ptr--;
  240.     *ptr = (unsigned char)(value & 0xFF);
  241.     value = value >> 8;
  242.   }
  243.   if(value != 0)
  244.     panic("In a call to write_bytes_to_memory, the value %ld can not be represented in %ld bytes", original_value, size);
  245.  
  246.   return(size);
  247. }
  248.         
  249. /* adds a word to the hashtable. Returns the 0 if successful. 
  250.    See irext.h for more documentation.
  251.  */
  252. long add_word(word, char_pos, line_pos,
  253.           weight, doc_id, date, word_pair, db, word_position)
  254.      char *word;    /* the word to be indexed, this could be a
  255.                word pair. If NULL there are no more words
  256.                to be indexed */
  257.      long char_pos;    /* the position of the start of the
  258.                word */
  259.      long line_pos;    /* this is passed for the best
  260.                section calculation */
  261.      long weight;    /* how important the word looks
  262.                syntactically (such as is it bold)
  263.                NOT used by signature system */
  264.      long doc_id;     /* current document, this will never be 0 */
  265.      time_t date; /* display day of this document, 0 if not known */
  266.      long word_pair;
  267.      database* db; /* database to insert the document */
  268.      boolean word_position; /* whether to have multiple entries for words in a document */
  269. {
  270.   /* look up the word in the hashtable */
  271.   /* creates it if necessary */    
  272.   hash_entry* wrd_entry;
  273.   hashtable * the_word_memory_hashtable = db->the_word_memory_hashtable;
  274.   /* printf("Word: '%s' doc_id: %ld, pos: %ld, weight: %ld\n",
  275.      word, doc_id, char_pos, weight); */
  276.   
  277.   if(NULL == db->the_word_memory_hashtable){
  278.     panic("The memory word hashtable is not defined.");
  279.   }
  280.  
  281.   /* if we have indexed enough words flush the memory copies to disk. */
  282.   if(db->number_of_words_in_hashtable == db->flush_after_n_words)
  283.     flush_memory_hashtable_to_disk(db, false);
  284.  
  285.   wrd_entry = look_up_word(word, the_word_memory_hashtable);
  286.   wrd_entry->number_of_occurances ++;
  287.  
  288.   if(wrd_entry->number_of_occurances > MAX_OCCURANCES){
  289.     /* do nothing. we have enough of that word */
  290.   }
  291.   else{
  292.     /* we have a word to add */
  293.     db->number_of_words_in_hashtable ++;
  294.  
  295.     if(word_position || doc_id != wrd_entry->current_doc_id){
  296.       /* then we have a new doc_id to add to the memory block */
  297.           
  298.       /* check to see if we need more memory */
  299.       if((wrd_entry->memory_size -
  300.       (wrd_entry->current_memory_ptr - 
  301.        wrd_entry->memory_ptr) 
  302.       < 
  303.       INDEX_ELEMENT_SIZE)){
  304.     /* we need more memory. this makes more and frees the old*/
  305.     unsigned char* old_memory_ptr = wrd_entry->memory_ptr;
  306.  
  307.     long new_size = 
  308.       more_memory_size(wrd_entry->memory_size,
  309.                wrd_entry->number_of_occurances);
  310.     /* cprintf(PRINT_AS_INDEXING, "Get more memory %ld bytes for %s\n", new_size, word); */
  311.     wrd_entry->memory_ptr = 
  312.       more_memory(wrd_entry->memory_ptr, wrd_entry->memory_size,
  313.               new_size);
  314.     wrd_entry->current_memory_ptr = 
  315.       wrd_entry->memory_ptr + /* new offset */
  316.         (wrd_entry->current_memory_ptr - old_memory_ptr);
  317.     /* just being paranoid... no longer illegal
  318.        if(wrd_entry->current_memory_ptr == wrd_entry->memory_ptr)
  319.        panic("After allocating more memory, the size went to 0");
  320.        */
  321.     wrd_entry->memory_size = new_size;
  322.       }                /* finished making more memory */
  323.  
  324.       /* add away */
  325.       wrd_entry->current_memory_ptr +=
  326.     write_bytes_to_memory(doc_id, DOCUMENT_ID_SIZE,
  327.                   wrd_entry->current_memory_ptr);
  328.       wrd_entry->current_memory_ptr +=
  329.     write_bytes_to_memory(char_pos, 
  330.                   CHARACTER_POSITION_SIZE,
  331.                   wrd_entry->current_memory_ptr);
  332.       wrd_entry->current_memory_ptr +=
  333.     write_bytes_to_memory(weight +
  334.                    /* add 5 since for the first one */
  335.                   (doc_id != wrd_entry->current_doc_id)?5:0,
  336.                   WEIGHT_SIZE,
  337.                   wrd_entry->current_memory_ptr);
  338.       wrd_entry->current_doc_id = doc_id;
  339.  
  340.     }
  341.     else{
  342.       /* The word is already there,
  343.        * just increment the weight in the record.
  344.        * This will change when/if position information is kept (for proximity).
  345.        */
  346.       if(wrd_entry->current_memory_ptr == wrd_entry->memory_ptr){
  347.     panic("Memory hashtable error. Recorded doc_id %ld, current doc_id %ld\n",
  348.           wrd_entry->current_doc_id, doc_id);
  349.       }
  350.       *(wrd_entry->current_memory_ptr - 1) =
  351.     add_weight(*(wrd_entry->current_memory_ptr - 1), weight);
  352.     }
  353.   }
  354.   return(0L);
  355. }
  356.  
  357. void add_stop_words(the_word_memory_hashtable)
  358. hashtable *the_word_memory_hashtable;
  359.      /* add the stop words to the hashtable.  this must be done before
  360.     adding other words */
  361. {
  362.   init_stop_list();
  363.   while(true){
  364.     char *word = next_stop_word();
  365.     hash_entry* wrd_entry;
  366.  
  367.     if(NULL == word)
  368.       break;
  369.     wrd_entry = look_up_word(word, the_word_memory_hashtable);
  370.     wrd_entry->number_of_occurances = STOP_WORD_FLAG;
  371.   }
  372. }
  373.  
  374.